/**
 * 使用位运算实现加减乘除操作
 */


public class _Java位运算加减乘除 {
    public static void main(String[] args) {
        int a = 13, b = 9;
        int target = multipication(a, b);
        System.out.println(target);
    }

    /**
     * 递归加法
     * 13二进制为1101，9二进制为1001。
     * 不考虑进位结果为0100。算式为a^b
     * 只考虑进位结果为10010。算式为（a&b）<< 1
     * 然后它俩继续进行运算，直到进位为0。
     * @param a
     * @param b
     * @return
     */
    public static int add(int a, int b) {
        // 当进位值为0的时候，第一个数就是结果
        if (b == 0) {
            return a;
        }else {
            // 进位值
            int carry = (a & b) << 1;
            // 异或相当于不进位加法
            a = a ^ b;
            return add(a, carry);
        }
    }

    /**
     * 非递归加法
     * @param a
     * @param b
     * @return
     */
    public static int add2(int a, int b) {
        // 进位值
        int carry;
        while (b != 0) {
            carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }

    /**
     * 乘法
     * 二进制乘法的原理是：从乘数的低位到高位，遇到1并且这个1在乘数的右起第i（i从0开始数）位，
     * 那么就把被乘数左移i位得到 temp_i 。直到乘数中的1遍历完后，把根据各位1而得到的被乘数的左移值们 temp_i 相加起来即得乘法结果。
     * 那么根据这个原理，可以得到实现代码：这里要点为：用i记录当前遍历的乘数位,当前位为1则被乘数左移i位并加到和中，同时i++处理下一位；
     * 为0则乘数右移，i++，处理下一位......直到乘数==0说明乘数中的1遍历完了。此时把和返回即可。
     * @param a
     * @param b
     * @return
     */
    public static int multipication(int a, int b) {
        // 当前遍历的乘位数
        int i = 0;
        // 最后结果
        int res = 0;
        while (b != 0) {
            // 处理当前位置
            // 当前位置是1
            if ((b & 1) == 1) {
                res += (a << i);
                b = b >> 1;
                // 记录当前是第几位
                i++;
            }else {
                // 当前位是0
                b = b >> 1;
                i++;
            }
        }
        return res;
    }

    /**
     * 减法 先来证明一个等式。Java负数存储是以补码形式存储的（补码=反码+1）。所以反码=补码-1.即~n=-n-1=-(n+1)
     * 所以a-b可以化简为a+(-b)=a+~b+1
     * @param a
     * @param b
     * @return
     */
    public static int subtraction(int a, int b) {
        b = ~b + 1;
        return add(a, b);
    }

    /**
     * 除法:求a可以由多少个b组成，也即求a能减去多少个b，做减法的次数就是除法的商
     * @param a
     * @param b
     * @return
     */
    public static int division(int a, int b) {
        int res;
        if (a < b) {
            return 0;
        }else {
            res = division(subtraction(a, b), b) + 1;
        }
        return res;
    }
}
